package com.dylan.历史.领扣;

/**
 * @Auther: ankang
 * @Date: 2019/2/22 21:20
 * @Description:
 */
public class $0060第K个排列 {

    public static void main(String[] args) {
        String result = new Solution().getPermutation(4, 2);
        System.out.println(result);
    }

    static class Solution {
        public String getPermutation(int n, int k) {
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = i + 1;
            }
            getPermutationDo(result, n, k - 1);
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < result.length; i++) {
                builder.append(result[i]);
            }
            return builder.toString();
        }

        public void getPermutationDo(int[] result, int n, int k) {
            if (k == 0) {
                return;
            }
            int m = 1;
            int idx = n-1;
            for (int i = 1; i <= n; i++) {
                if (m * i <= k) {
                    m = m * i;
                    idx--;
                } else {
                    int t = k / m + idx;
                    fromTo(result, t, idx);
                    k = k % m;
                    getPermutationDo(result, n, k);
                    break;
                }
            }
        }

        public void fromTo(int[] result, int from, int to) {
            if (from > to) {
                int fromValue = result[from];
                System.arraycopy(result, to, result, to + 1, from - to);
                result[to] = fromValue;
            } else if (from < to) {
                fromTo(result, to, from);
            }
        }
    }
}
